package com.gitee.feizns.explore.data_structure.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author feizns
 * @since 2020/2/27
 */
public class CloneGraph {

    public static void main(String[] args) {
        Node node = cloneGraph(null);
        System.out.println(node.val);
    }

    private static Node graph() {
        Node t = new Node(1);
        Node w = new Node(2);
        t.neighbors.add(w);
        w.neighbors.add(t);
        return t;
    }

    private static Map<Integer, Node> CACHE = new HashMap<>();

    public static Node cloneGraph(Node node) {
        if ( CACHE.containsKey(node.val) )
            return CACHE.get(node.val);
        Node ret = new Node(node.val);
        CACHE.put(node.val, ret);
        for (Node n : node.neighbors)
            ret.neighbors.add(cloneGraph(n));
        return ret;
    }

    static class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

}
